package spaska.classifiers;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.logging.Logger;

import spaska.data.Attribute.ValueType;
import spaska.data.Dataset;
import spaska.data.Instance;
import spaska.data.NumericValue;
import spaska.data.Value;

/**
 * 
 * @author Lazar Chifudov
 */

/* Implementation of the K-Nearest Neighbor classifier */
public class KNN implements IClassifier {

	private static final Logger logger = Logger.getLogger(KNN.class.getName());

	private static final int DEFAULT_K = 9;
	private int k;
	private boolean weighted;
	private DistanceQueue distanceQueue; // queue to store distances
	private List<Instance> trainSet; // list pruned of classless instances
	private Dataset originalTrainSet; // the given train set
	// //for optimization
	private ValueType[] attrTypes;
	private Value[] queryVectorArray;

	public static Map<String, String> getParameters() {
		Map<String, String> result = new HashMap<String, String>();
		result.put("k", "9");
		result.put("weighted", "false");
		return result;
	}

	public KNN() {
		setK(DEFAULT_K);
	}

	/* A class representing a measured distance and the corresponding instance */
	private class Pair {

		double distance;
		Instance instance;

		public Pair(double distance, Instance instance) {
			this.distance = distance;
			this.instance = instance;
		}

		public Pair() {
			this(Double.MAX_VALUE, null);
		}
	}

	/* A fixed size queue for storing distances and the corresponding instances */
	private class DistanceQueue {

		Pair[] distances; // the queue

		// construct the queue given the classifier parameter K
		DistanceQueue(int k) {
			distances = new Pair[k];
		}

		// set default values
		void clear() {
			for (int i = 0; i < distances.length; ++i) {
				distances[i] = new Pair();
			}
		}

		/*
		 * insert a pair it its proper place in the queue keeping the queue
		 * sorted
		 */
		void push(double distance, Instance instance) {
			if (distance >= distances[0].distance) {
				return; // do not insert if value is worse than the worst in
				// queue
			}

			int index = 0;
			// find the correct index of the new pair
			while (index < distances.length && distance < distances[index].distance) {
				++index;
			}
			--index;
			// shift previous pairs and insert
			for (int i = 0; i < index; ++i) {
				distances[i] = distances[i + 1];
			}
			distances[index] = new Pair(distance, instance);
		}

		/*
		 * returns the most frequent class value (if discrete) or mean of class
		 * values (if numeric) in the queue
		 */
		Value voteForClass() {
			ValueType type = originalTrainSet.getClassAttribute().getType();
			// 1st case: numeric class value
			if (type == ValueType.Numeric) {
				double sum = 0.0, sumWeights = 0.0;
				for (int i = 0; i < distances.length; ++i) {
					if (distances[i].distance == 0.0) {
						return distances[i].instance.classValue();
					}
					double weight = weighted ? (1 / distances[i].distance) : 1.0;
					sumWeights += weight;
					sum += weight * (Double) (distances[i].instance.classValue().getValue());
				}
				return new NumericValue(sum / sumWeights);
			} // 2nd case: nominal class value
			else {
				// a map for storing frequencies/weights
				Map<Value, Double> frequencies = new HashMap<Value, Double>();
				for (int i = 0; i < distances.length; ++i) {
					if (distances[i].distance == 0.0) {
						return distances[i].instance.classValue();
					}
					Value currentClass = distances[i].instance.classValue();
					Double oldValue = frequencies.get(currentClass);
					// set weight or frequency
					double weight = weighted ? (1 / distances[i].distance) : 1.0;
					if (weight == Double.NaN) {
						weight = 1.0;
					}
					if (oldValue == null) {
						frequencies.put(currentClass, weight);
					}
					else {
						frequencies.put(currentClass, oldValue + weight);
					}
				}
				// traverse the map to find the most frequent class value
				Iterator<Value> it = frequencies.keySet().iterator();
				double maxFrequency = Double.MIN_VALUE;
				Value result = null;
				while (it.hasNext()) {
					Value currentClass = it.next();
					Double currentFrequency = frequencies.get(currentClass);
					/*
					 * System.out.print(currentClass + " -> ");
					 * System.out.println(currentFrequency);
					 */
					if (currentFrequency > maxFrequency) {
						maxFrequency = currentFrequency;
						result = currentClass;
					}
				}
				// System.out.println("returned class: " + result);
				return result;
			}
		}
	}

	/* return the KNN parameter K */
	public int getK() {
		return k;
	}

	/* set the KNN parameter K */
	public void setK(int k) {
		if (k < 1) { // if illegal value given, set to default
			logger.warning("Invalid value for k. Setting k = " + DEFAULT_K);
			k = DEFAULT_K;
		}
		this.k = k;
		// also create the distance queue
		distanceQueue = new DistanceQueue(this.k);
	}

	/* weighted or not */
	public boolean isWeighted() {
		return weighted;
	}

	/* set weighted or not */
	public void setWeighted(boolean weighted) {
		this.weighted = weighted;
	}

	/**
	 * Fills the queue with distances from the query instance to its K nearest
	 * neighbors
	 */
	private void calculateDistances(Instance query) {
		Value[] queryVector = query.getVector();
		// for optimization
		queryVectorArray = Arrays.copyOf(queryVector, queryVector.length);

		for (Instance currentInstance : trainSet) {
			double result = 0;
			for (int i : originalTrainSet.getEvaluationIndices()) {
				Value currentValue = currentInstance.valueAt(i);
				result += distanceBetweenValues(queryVectorArray[i], currentValue, attrTypes[i]);
			}
			result = Math.sqrt(result); // distance is Euclidean
			distanceQueue.push(result, currentInstance);
		}
	}

	/* returns the distance between two values, given their type */
	private double distanceBetweenValues(Value queryValue, Value currentValue, ValueType attrType) {
		// 1st case: nominal values
		if (attrType == ValueType.Nominal) {
			if (queryValue.getType() != ValueType.Unknown && currentValue.getType() != ValueType.Unknown) {
				if (!queryValue.equals(currentValue)) {
					return 1;
				}
			}
			else if (queryValue.getType() == ValueType.Unknown && currentValue.getType() == ValueType.Unknown) {
				return 0;
			}
			else {
				return 1;
			}
		} // 2nd case: numeric values
		else if (attrType == ValueType.Numeric) {
			if (queryValue.getType() != ValueType.Unknown && currentValue.getType() != ValueType.Unknown) {
				double dst = (Double) queryValue.getValue() - (Double) currentValue.getValue();
				return dst * dst;
			}
			else if ((queryValue.getType() == ValueType.Unknown && currentValue.getType() == ValueType.Unknown)) {
				return 0;
			}
			else {
				return 1;
			}
		}
		return 0;
	}

	/* train the knn classifier */
	public void train(Dataset instances) {
		originalTrainSet = instances;
		trainSet = new ArrayList<Instance>(originalTrainSet.size());

		for (Instance current : originalTrainSet) { // prune instances with
													// missing class value
			if (current.classValue().getType() != ValueType.Unknown) {
				trainSet.add(current);
			}
		}
		// set attribute types array
		attrTypes = originalTrainSet.getAttributeTypes();

		if (k > trainSet.size()) {
			setK(trainSet.size());
			logger.warning("KNN: k >= all neighbors! Setting k to dataset size.");
		}
	}

	/** classify an instance after training */
	public Value classifyInstance(Instance instance) {
		distanceQueue.clear();
		calculateDistances(instance);
		return distanceQueue.voteForClass();
	}

	/* should be called after setting parameters */
	public String getName() {
		return "K-Nearest Neighbor (k=" + k + (weighted ? "; weighted)" : ")");
	}

	@Override
	public void setParameters(Map<String, String> parameters) {
		for (String key : parameters.keySet()) {
			String value = parameters.get(key);
			setParameter(key, value);
		}
	}

	private void setParameter(String paramName, String paramValue) {
		if (paramName.equalsIgnoreCase("k")) {
			int kValue;
			try {
				kValue = Integer.parseInt(paramValue);
			}
			catch (NumberFormatException ex) {
				kValue = DEFAULT_K;
				throw new RuntimeException("\"k\" must be an integer.");
			}
			setK(kValue);
		}
		else if (paramName.equalsIgnoreCase("weighted")) {
			if (paramValue.equalsIgnoreCase("true")) {
				setWeighted(true);
			}
			else if (paramValue.equalsIgnoreCase("false")) {
				setWeighted(false);
			}
			else {
				throw new RuntimeException("\"weighted\" must be boolean.");
			}
		}
		else {
			throw new IllegalArgumentException("KNN: unknown parameter (valid: K; Weighted)");
		}
	}

	@Override
	public String toString() {
		return String.format("K Nearest Neighbour\n  - weighted : %s\n  - k : %d", weighted, k);
	}
}
